import pdb
result = []
ip_result = []
def is_valid(s):
    if len(s)>=2 and not s.startswith('0') and int(s)<=255:
        return True
    elif len(s) == 1:
        return True
    else:
        return False
def restoreIpAddresses(s):
    for i in range(1,4):
        current_s = s[:i]
        if is_valid(current_s):
            result.append(current_s)
            if len(result)<4:
                restoreIpAddresses(s[i:])
            elif len(result)==4 and len(s)>3:
                print("debug current result: {} ,str :{}".format(result,s))
                result.pop(-1)
                continue
    if len(result)==4 and is_valid(s):
        ip_result.append(".".join(result))
        return ip_result
    elif len(result)>0 and len(s)>3:
        result.pop(-1)

def main():
    restoreIpAddresses("25525511135")
    print(ip_result)
if __name__ == "__main__":
    main()
